/**
 * 
 */
package leetCode;

import java.util.*;

/**
 * @author zhongfang
 *
 */
public class regularexpressionmatching {
	int[][] matched;//0没有比较过，1
    public boolean isMatch(String s, String p) {
    	matched=new int[s.length()+1][p.length()+1];
    	boolean[][] match=new boolean[s.length()][p.length()];
    	
    	for(int i=0;i<s.length();i++){
    		for (int j = 0; j < p.length(); j++) {
				if(p.charAt(j)=='*'){
					if(s.charAt(i)==p.charAt(j)||p.charAt(j)=='.'){
						match[i][j]=match[i][j-2]||match[i][j-1]||match[i-1][j];
					}else {
						match[i][j]=j<2?true:match[i][j-2];
					}
				}
				if(s.charAt(i)==p.charAt(j)||p.charAt(j)=='.'){
					match[i][j]=i==0||j==0?true:match[i-1][j-1];
				}
			}
    	}
        return match[s.length()-1][p.length()-1];
    }
    
    public boolean isMatch(String s,String p,int i,int j){
        if(i==s.length()&&j==p.length()){
            return true;
        }else if(j==p.length()){
            return false;
        }
        if(j<p.length()-1&&p.charAt(j+1)=='*'){//无限个
            if(p.charAt(j)=='.'){//无限个任意字符
                //0个,1个,多个
                return isMatch(s,p,i,j+2)||isMatch(s,p,i+1,j+2)||isMatch(s,p,i+1,j);
            }else{//无限个指定字符
                if(i!=s.length()&&s.charAt(i)!=s.charAt(j)){
                    return isMatch(s,p,i,j+2);//0
                }else{
                    return isMatch(s,p,i+1,j+2)||isMatch(s,p,i+1,j);
                }
        	}
        }
        if(p.charAt(j)=='.'){//任意一个字符
            return isMatch(s,p,i+1,j+1);//向前走一步
        }
        return i<s.length()&&s.charAt(i)==p.charAt(j)&&isMatch(s,p,i+1,j+1);//相等并且向前走一步
    }
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		regularexpressionmatching regularexpressionmatching=new regularexpressionmatching();
		String s="aa";
		String p="a";
		System.out.println(regularexpressionmatching.isMatch(s, p));;

	}

}
